package problems.practice;

import java.util.List;

/**
 * 524. 通过删除字母匹配到字典里最长单词
 * <p>https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/</p>
 * <p></p>
 * @author habitplus
 * @since 2022/8/14 15:31
 */
public class T524 {
    public String findLongestWord(String s, List<String> dictionary) {
        // 排序
        dictionary.sort((s1, s2) -> {
           if (s1.length() != s2.length())
               return s2.length() - s1.length();
           else
               return s1.compareTo(s2);
        });

        char[] chs = s.toCharArray();
        int n1 = chs.length;
        int n2, i, j;
        for (String d : dictionary) {
            //判断 d 是否为 s 的子序列：贪心
            i = 0;
            j = 0;
            n2 = d.length();
            while (i < n1 && j < n2) {
                if (chs[i] == d.charAt(j)) ++j;
                ++i;
            }

            if (j == n2) return d;
        }
        return "";
    }
}
